/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package memoryManagement;

/**
 *
 * @author feiyun
 */
import java.util.ArrayList;
import java.util.Stack;
import javax.swing.JFrame;

/**
 *
 * @author xyc
 */
public class mem {

    private int size;//mem大小
    private ArrayList freeList = new ArrayList();//用于找寻空闲buddy链表

    //private int mark ;//作为标志画图用
    /*
     空闲的buddy链表
     1～8代表4～512kb
     */
    private Stack freeStack1 = new Stack();
    private Stack freeStack2 = new Stack();
    private Stack freeStack3 = new Stack();
    private Stack freeStack4 = new Stack();
    private Stack freeStack5 = new Stack();
    private Stack freeStack6 = new Stack();
    private Stack freeStack7 = new Stack();
    private Stack freeStack8 = new Stack();
    public displayPanel frame;//显示内存情况的窗口
    private buddy m = new buddy();//最初的buddy
    protected program pList = new program();//内存程序链

    public mem(int size) {
        this.size = size;
        m = new buddy();
        freeStack8.push(m);
        this.freeList.add(freeStack1);
        this.freeList.add(freeStack2);
        this.freeList.add(freeStack3);
        this.freeList.add(freeStack4);
        this.freeList.add(freeStack5);
        this.freeList.add(freeStack6);
        this.freeList.add(freeStack7);
        this.freeList.add(freeStack8);

    }

    public mem() {
        this.size = 512;
        this.freeStack8.push(m);
        this.freeList.add(freeStack1);
        this.freeList.add(freeStack2);
        this.freeList.add(freeStack3);
        this.freeList.add(freeStack4);
        this.freeList.add(freeStack5);
        this.freeList.add(freeStack6);
        this.freeList.add(freeStack7);
        this.freeList.add(freeStack8);
        frame = new displayPanel(this);
    }

    //对外展示的创建程序的接口,需要程序pid与大小，返回ture则创建成功，如果失败则返回false
    public boolean create(int pid, int size) {
        boolean a = createProcedure(pid, size);
        frame.rePaint(this);//for(int i =0 ;i<999999999;i++);
        return a;
    }

    //对外展示的释放程序的接口,需要程序pid，返回ture则释放成功，如果失败则返回false
    public boolean release(int pid) {
        boolean a = releaseProcedure(pid);//释放程序
        frame.rePaint(this);//for(int i =0 ;i<999999999;i++);//重画并延时显示
        return a;
    }

    private boolean createProcedure(int pid, int size) {
        //如果有buddy可以接受这个大小则继续执行
        if (size <= 4) {
            size = 1;
        } else if (size <= 8) {
            size = 2;
        } else if (size <= 16) {
            size = 3;
        } else if (size <= 32) {
            size = 4;
        } else if (size <= 64) {
            size = 5;
        } else if (size <= 128) {
            size = 6;
        } else if (size <= 256) {
            size = 7;
        } else if (size <= 512) {
            size = 8;
        } else {
            //超过了512mb内存不够用返回false
            return false;
        }
        //getbuddy这个方法如果成功，那么必须有一个适合当前程序的buddy在空闲链表中
        if (!getBuddy(size)) {
            return false;
        }
        Stack buff = (Stack) freeList.get(size - 1);
        program p = new program(pid, (buddy) buff.pop());
        //创建第一个程序的必要初始化
        if (pList.lLink == null) {
            pList.lLink = p;
            p.fLink = pList;
            p.lLink = null;
        } else {
            //初始化之后的程序连在最后一个program的后面
            program buffer;
            buffer = pList.lLink;
            while (true) {
                /*如果pid相同则不允许创建，但是已经得到的buddy还是在原位置不再合并
                    
                 */
                if (buffer.pid == pid) {
                    return false;
                }
                if (buffer.lLink == null) {
                    buffer.lLink = p;
                    p.fLink = buffer;
                    p.lLink = null;
                    break;
                }
                buffer = buffer.lLink;
            }
        }

        return true;

    }

    //判断内存是否够这一个程序，若够则把程序大小合适的buddy放入空闲链表freelist
    private boolean getBuddy(int size) {
        int i = size;
        while (i <= 8) {
            Stack st = (Stack) freeList.get(i - 1);
            //找到可以使用的buddy
            if (!st.isEmpty()) {
                //如果找到可以使用的buddy就切割并返回true
                if (size != i) {
                    for (; i > size; i--) {
                        /*
                         找到buddy切割方法用其中大于等于size最小的buddy依次切下来
                         */
                        buddy buff = (buddy) st.pop();
                        buddy buff1 = new buddy(buff.size / 2, buff.fPage, (buff.lPage + buff.fPage - 1) / 2);//左伙伴
                        buddy buff2 = new buddy(buff.size / 2, (buff.lPage + buff.fPage + 1) / 2, buff.lPage);//右伙伴
                        st = (Stack) freeList.get(i - 2);
                        st.push(buff2);
                        st.push(buff1);
                    }
                }
                return true;
            }
            i++;
        }
        return false;
    }
    /*
     释放一个进程
     */

    private boolean releaseProcedure(int pid) {
        program aim;
        buddy buff;
        aim = pList.lLink;
        while (aim != null) {
            //找到aim的伙伴
            if (aim.pid == pid) {
                int size = (int) (Math.log(aim.ownMem.size) / Math.log(2)) - 2;
                buff = aim.ownMem;
                while (true) {
                    buddy friend = findFreeFriend(buff);
                    /*
                     先搜索是否存在空闲伙伴，
                     没有空闲伙伴则直接压入对应空闲栈,如果有则合并再次执行
                     */
                    if (friend == null) {
                        Stack aimStack = (Stack) freeList.get(size);
                        aimStack.push(buff);
                        break;
                    } else {
                        buff.size = 2 * buff.size;
                        ++size;
                        if (buff.fPage < friend.fPage) {
                            buff.lPage = friend.lPage;
                        } else {
                            buff.fPage = friend.fPage;
                        }
                    }
                }
                //从程序链中释放
                if (aim.lLink != null) {
                    aim.lLink.fLink = aim.fLink;
                }
                aim.fLink.lLink = aim.lLink;

                return true;

            }
            aim = aim.lLink;

        }
        return false;
    }

    //找自己的空闲伙伴，找到返回伙伴，没有就返回null
    private buddy findFreeFriend(buddy aim) {
        buddy friend = null;//返回值
        Stack buff = new Stack();//用于暂时存储找寻伙伴所pop出来的buddy（从freeStack？中取出的）
        int size = (int) (java.lang.Math.log((double) aim.size) / java.lang.Math.log(2.0)) - 2;//用于找出aim的伙伴处于哪一个freeStack
        int fPage = aim.fPage;//firend's fPage
        int lPage = aim.lPage;//friend's lPage
        //判断是否为右伙伴
        if ((aim.fPage - 1) % (aim.size / 2) == 0) {
            fPage = aim.fPage + aim.size / 4;
            lPage = aim.lPage + aim.size / 4;
        } else {
            fPage = aim.fPage - aim.size / 4;
            lPage = aim.lPage - aim.size / 4;
        }

        Stack aimStack = (Stack) freeList.get(size);//得到合适大小的空闲buddy栈
        /*
         判断aim的伙伴是否在空闲栈中，其中pop出来的元素压入buff，如果找到则跳出循环
         */
        while (!aimStack.empty()) {
            buddy f = (buddy) aimStack.pop();
            if (f.fPage == fPage) {
                friend = f;
                break;
            }
            buff.push(f);
        }
        //将buff的元素还原
        while (!buff.empty()) {
            aimStack.push(buff.pop());
        }
        return friend;
    }

    //建立一个窗口显示当前内存使用情况 
    public void display() {

        //frame.setTitle("内存情况分析图");
        //frame.setSize(1104, 400);
        //frame.setLocationRelativeTo(null);
        //frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        //frame.setVisible(true);
        // for(int ll=0;ll<999999999;ll++);
    }
}
